package com.dycong.common.leetcode.any;

import com.dycong.common.leetcode.ds.ListNode;

import java.util.Arrays;

/**
 * 作用描述:
 *
 * @author dycong
 * @date 2020/1/8 8:34
 */
public class ReplaceSpace {

    public static void main(String[] args) {
        StringBuilder builder = new StringBuilder(" a b c d  e ");
        System.out.println(replaceSpace(builder));
        System.out.println(integerBreak(5));
        System.out.println(JumpFloorII(5));
        System.out.println(JumpFloorII2(5));
        ListNode head = new ListNode(1);
        ListNode node_2 = new ListNode(2);
        ListNode node_3 = new ListNode(2);
        ListNode node_4 = new ListNode(3);
        ListNode node_5 = new ListNode(3);
        ListNode node_6 = new ListNode(4);

        head.next = node_2;
        node_2.next = node_3;
        node_3.next = node_4;
        node_4.next = node_5;
        node_5.next = node_6;
        System.out.println(ListNode.format(head));
        System.out.println(ListNode.format(deleteDuplication(head)));
    }

    public static String replaceSpace(StringBuilder str) {
        int p1 = str.length() - 1;

        for (int i = 0; i <= p1; i++) {
            if (' ' == str.charAt(i)) {
                str.append("  ");
            }
        }
        int p2 = str.length() - 1;

        while (p1 >= 0 && p2 > p1) {
            char c = str.charAt(p1--);
            if (' ' == c) {
                str.setCharAt(p2--, '0');
                str.setCharAt(p2--, '2');
                str.setCharAt(p2--, '%');
            } else {
                str.setCharAt(p2--, c);
            }

        }


        return str.toString();
    }

    /**
     * 剪绳子+ 动态规划
     */

    public static int integerBreak(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                //一些场景下 j * (i - j) 为最大值；例如n=4
                dp[i] = Math.max(dp[i], Math.max(dp[j] * (i - j), j * (i - j)));
            }
        }
        return dp[n];
    }

    /**
     * 跳上 n-1 级台阶，可以从 n-2 级跳 1 级上去，也可以从 n-3 级跳 2 级上去...，那么
     * 所以 f(n) 是一个等比数列
     * 1  1
     * 2  2
     * 3  4
     *
     * @param target
     * @return
     */
    public static int JumpFloorII(int target) {
        return (int) Math.pow(2, target - 1);
    }

    /**
     * 跳上 n-1 级台阶，可以从 n-2 级跳 1 级上去，也可以从 n-3 级跳 2 级上去...，那么
     * 初始化数组值全为1是因为也可以一次跳 n 直接跳上来
     *
     * @param target
     * @return
     */
    public static int JumpFloorII2(int target) {
        int[] dp = new int[target];
        Arrays.fill(dp, 1);
        for (int i = 1; i < target; i++) {
            for (int j = 0; j < i; j++) {
                dp[i] += dp[j];
            }
        }
        return dp[target - 1];
    }


    public static ListNode deleteDuplication(ListNode pHead) {
        if (pHead == null || pHead.next == null) {
            System.out.println("1 pHead" + ListNode.format(pHead));
            return pHead;
        }
        ListNode next = pHead.next;
        if (pHead.val == next.val) {
            while (next != null && pHead.val == next.val) {
                next = next.next;
            }
            System.out.println("2 pHead: " + ListNode.format(pHead) + "  ,next: " + ListNode.format(next));
            return deleteDuplication(next);
        } else {
            pHead.next = deleteDuplication(pHead.next);
            System.out.println("3 pHead: " + ListNode.format(pHead) + "  ,next: " + ListNode.format(next));
            return pHead;
        }
    }

}
